package com.silence.ByteDance;

public class easy_74x {
    public static int solution(int n, int g, int s, int[][] array) {
        // Edit your code here
        // n是能力数，g是金币，s是攻击速度
        // array中每个元素：金币，对攻击速度的影响，对攻击力的影响
        int[][] V = new int[n + 1][g + 1];
        int[][] S = new int[n + 1][g + 1];
        for (int i = 0; i <= n; i++) {
            V[i][0] = 0;
            S[i][0] = s;
        }
        for (int i = 0; i <= g; i++) {
            V[0][i] = 0;
            S[0][i] = s;
        }

        for (int i = 1; i <= n; i++) {
            int cost = array[i - 1][0];
            int speedEffect = array[i - 1][1];
            int attackEffect = array[i - 1][2];

            for (int j = 1; j <= g; j++) {
                if (cost <= j && speedEffect < S[i - 1][j]) {  // 放得下且攻速减少不低于0
                    if (V[i - 1][j] > V[i - 1][j - cost] + attackEffect) {
                        V[i][j] = V[i - 1][j];
                        S[i][j] = S[i - 1][j];
                    } else {
                        V[i][j] = V[i - 1][j - cost] + attackEffect;
                        S[i][j] = S[i - 1][j - cost] - speedEffect;
                    }

                } else {
                    V[i][j] = V[i - 1][j];
                    S[i][j] = S[i - 1][j];
                }
            }
        }

        return V[n][g];
    }

    public static void main(String[] args) {
        // Add your test cases here
        int[][] test1 = {
                {71, 51, 150},
                {40, 50, 100},
                {40, 50, 100},
                {30, 30, 70},
                {30, 30, 70},
                {30, 30, 70}
        };
        System.out.println(solution(6, 100, 100, test1));

        int[][] test2 = {
                {71, -51, 150},
                {40, -50, 100},
                {40, -50, 100},
                {30, -30, 70},
                {30, -30, 70},
                {30, -30, 70}
        };
        System.out.println(solution(6, 100, 100, test2));
    }
}
